/**
 * @file PreThreadBinaryTree.c
 * @desc 前序线索二叉树的基本实现（构建、线索化与遍历示例）
 * @author WangBlue(wangjiping596@gmail.com)
 * @date 2025/10/15 14:13
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * @struct BinNode
 * @brief 二叉树节点结构（带前序线索）
 *
 * ltag / rtag 含义：
 * - 0 表示对应指针是“孩子指针”
 * - 1 表示对应指针是“线索指针”
 */
typedef struct BinNode {
    char data;                    // 节点数据
    struct BinNode *lChild;       // 左孩子或前驱线索
    struct BinNode *rChild;       // 右孩子或后继线索
    struct BinNode *parent;       // 父节点指针（便于查找前驱）
    int ltag, rtag;               // 线索标志
} BinNode;


/**
 * @brief 创建一个新的二叉树节点
 *
 * @param data 节点存储的数据
 * @return BinNode* 新创建的节点指针；若分配失败返回 NULL
 */
BinNode* createTreeNode(char data) {
    BinNode *node = (BinNode *)malloc(sizeof(BinNode));
    if (node == NULL) {
        return NULL;
    }
    node->data = data;
    node->lChild = node->rChild = node->parent = NULL;
    node->ltag = node->rtag = 0;
    return node;
}


/**
 * @brief 构建一棵简单的示例二叉树
 *
 * 树结构如下：
 *        A
 *       / \
 *      B   C
 *     / \
 *    D   E
 *
 * @return BinNode* 返回根节点指针
 */
BinNode* createSimpleTree() {
    BinNode* A = createTreeNode('A');
    BinNode* B = createTreeNode('B');
    BinNode* C = createTreeNode('C');
    BinNode* D = createTreeNode('D');
    BinNode* E = createTreeNode('E');

    // 建立孩子关系
    A->lChild = B;  A->rChild = C;
    B->lChild = D;  B->rChild = E;

    // 建立父指针
    B->parent = A;
    C->parent = A;
    D->parent = B;
    E->parent = B;
    return A;
}


/**
 * @brief 普通的前序遍历（未线索化）
 *
 * @param root 根节点
 */
void preOrder(BinNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    preOrder(root->lChild);
    preOrder(root->rChild);
}


/**
 * @brief 访问当前节点时建立“前驱-后继”线索关系
 *
 * @param root 当前访问节点
 * @param pre  指向上一个访问过的节点指针变量
 *
 * @details
 * - 若当前节点左孩子为空，则将其左指针指向“前驱”
 * - 若上一个访问节点的右孩子为空，则将其右指针指向“当前节点”
 */
void visit(BinNode* root, BinNode** pre) {
    if (root == NULL) return;

    // 建立当前节点的前驱线索
    if (root->lChild == NULL) {
        root->ltag = 1;
        root->lChild = *pre;
    }

    // 建立前驱节点的后继线索
    if ((*pre) && (*pre)->rChild == NULL) {
        (*pre)->rtag = 1;
        (*pre)->rChild = root;
    }

    // pre 指针向后移动
    *pre = root;
}


/**
 * @brief 对二叉树进行前序线索化
 *
 * @param root 根节点
 * @param pre  指向“前驱节点”的指针变量地址
 *
 * @note 递归按照“根 → 左 → 右”顺序处理。
 */
void preThreadBinaryTree(BinNode* root, BinNode** pre) {
    if (root == NULL) return;

    visit(root, pre);  // 访问当前节点并建立线索

    // 若左子树存在（不是线索），递归处理左子树
    if (root->ltag == 0)
        preThreadBinaryTree(root->lChild, pre);

    // 若右子树存在（不是线索），递归处理右子树
    if (root->rtag == 0)
        preThreadBinaryTree(root->rChild, pre);
}


/**
 * @brief 前序遍历输出（使用线索结构遍历）
 *
 * @param root 根节点
 *
 * @note 与普通前序遍历形式相似，但可以结合线索实现非递归版本。
 */
void preOrderTraverseThreaded(BinNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);

    if (root->ltag == 0)
        preOrderTraverseThreaded(root->lChild);

    if (root->rtag == 0)
        preOrderTraverseThreaded(root->rChild);
}


/**
 * @brief 获取前序遍历的第一个节点
 *
 * @param root 根节点
 * @return BinNode* 前序的第一个节点（即根节点）
 */
BinNode* firstNode(BinNode* root) {
    return root;
}


/**
 * @brief 获取节点的前驱节点（在前序线索二叉树中）
 *
 * @param node 当前节点
 * @return BinNode* 前驱节点指针，若不存在返回 NULL
 *
 * @details
 * 查找逻辑：
 * 1. 若 ltag == 1，左指针即为前驱；
 * 2. 否则根据父节点关系判断：
 *    - 若当前节点是父节点的左孩子 → 前驱是父节点；
 *    - 若是右孩子 → 前驱是父节点左子树的最右节点；
 * 3. 若找不到父节点，返回 NULL。
 */
BinNode* preNode(BinNode* node) {
    if (node == NULL) return NULL;

    // 情况①：有左线索 → 直接返回
    if (node->ltag == 1)
        return node->lChild;

    // 情况②：向上寻找
    BinNode* parent = node->parent;
    if (parent == NULL) return NULL;

    if (parent->lChild == node)
        return parent;  // 是左孩子 → 前驱为父节点
    else {
        // 是右孩子 → 前驱为父节点左子树的最右节点
        BinNode* p = parent->lChild;
        if (p == NULL) return parent;  // 防止空指针
        while (p->rtag == 0 && p->rChild)
            p = p->rChild;
        return p;
    }
}


/**
 * @brief 获取节点的后继节点（在前序线索二叉树中）
 *
 * @param node 当前节点
 * @return BinNode* 后继节点指针；若无后继返回 NULL
 *
 * @details
 * 按前序逻辑：
 * 1. 若有左孩子 → 左孩子为后继；
 * 2. 若无左孩子但有右孩子 → 右孩子为后继；
 * 3. 若左右孩子都无 → 直接返回右线索。
 */
BinNode* nextNode(BinNode* node) {
    if (node == NULL) return NULL;

    if (node->ltag == 0 && node->lChild)
        return node->lChild;
    else if (node->rtag == 0 && node->rChild)
        return node->rChild;
    else
        return node->rChild;  // 线索指针
}


/**
 * @brief 在前序线索二叉树中查找指定数据的节点
 *
 * @param node 根节点
 * @param target 要查找的字符
 * @return BinNode* 若找到返回节点指针，否则返回 NULL
 *
 * @details
 * 利用线索结构实现遍历：从 firstNode 开始，依次调用 nextNode。
 */
BinNode* findNode(BinNode* node, char target) {
    if (node == NULL) return NULL;

    for (BinNode* p = firstNode(node); p != NULL; p = nextNode(p)) {
        if (p->data == target)
            return p;
    }
    return NULL;
}


/**
 * @brief 主函数：测试前序线索二叉树的构建与遍历
 */
int main() {
    BinNode* root = createSimpleTree();  // 构建示例树

    printf("Original pre-order traversal:\n");
    preOrder(root);
    printf("\n");

    BinNode* pre = NULL;
    preThreadBinaryTree(root, &pre);     // 前序线索化

    if (pre) {
        pre->rtag = 1;
        pre->rChild = NULL;  // 明确最后一个节点的后继为空
    }

    printf("Pre-order traversal after threading:\n");
    preOrderTraverseThreaded(root);
    printf("\n");

    // 查找节点 E 并打印其前驱节点
    BinNode* E = findNode(root, 'E');
    BinNode* prNode = preNode(E);
    if (prNode) {
        printf("The predecessor of node E is: %c\n", prNode->data);
    }

    return 0;
}
